﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

/// <summary>
/// ---------------------------------------------------------------------------      
///                CopyRight. 2009 Dylan
///          
///  Owner:        Dylan
/// ---------------------------------------------------------------------------  
///  Purpose:      Investigate DataStructure
///  Abstract:          
///         About Generic: http://msdn.microsoft.com/zh-cn/library/ms379564(VS.80).aspx
///         
/// <history>
///          [Dylan]    9/01/2009       Created and add Generic Stack 
///          [Dylan]    9/08/2009       Add Generic LinkedList   
///          [Dylan]    4/21/2010       Update Generic LinkedList with comments, add unit tests for it
/// </history>
///---------------------------------------------------------------------------
/// </summary>
namespace SDFL.Core.DataStructure
{   

    /// <summary>
    /// Each node also has a reference to the next node in the list.
    /// 
    /// public class Node<K,T> where T: new()
    /// {...}
    /// This is constructor constraint, 
    /// constrain generic type 'T', it must support a public default constructor. 
    /// 
    /// public class Node<K,T> where K: struct
    /// {...}
    /// This is Reference/Value Type Constraint
    /// constrain the generic type parameter 'K' to be a value type (such as an int, a bool, and enum) or any custom structure.
    /// Similarly, you can constrain a generic type parameter to be a reference type (a class) using the class constraint: 
    /// public class MyClass<T> where T : class
    /// {...}
    /// 
    /// !!! Notice !!!
    /// If you define a constraint in base class, the derived class has a member variable of this base type,
    /// you MUST place the constraint at the derived class level as well 
    /// </summary>
    /// <typeparam name="K">key</typeparam>
    /// <typeparam name="T">value</typeparam>
    public class Node<K,T> where K: struct
                            where T : new()
    {
        public K m_Key;
        public T m_Item;

        public Node<K, T> NextNode;

        public Node()
        {
            m_Key = default(K);
            m_Item = new T();
            NextNode = null;
        }

        public Node(K key, T item, Node<K,T> nextNode)
        {
            m_Key = key;
            m_Item = item;
            this.NextNode = nextNode;
        }
    }

    /// <summary>
    /// The linked list itself is defined in terms of the generic type parameters K and T:
    /// </summary>
    /// <typeparam name="K">Key parameter</typeparam>
    /// <typeparam name="T">Value parameter</typeparam>
    public class LinkedList<K,T> where K: struct, IComparable
                                    where T: new()
    {
        private Node<K,T> m_Head;

        public Node<K, T> Head
        {
            get
            {
                return m_Head;
            }
        }

        public LinkedList()
        {
            this.m_Head = new Node<K,T>();
        }

        /// <summary>
        ///    Add a new node after the Head Node
        /// </summary>
        /// <param name="key"></param>
        /// <param name="item"></param>
        public void AddHead(K key, T item)
        {
            Node<K, T> newNode = new Node<K, T>(key, item, this.Head.NextNode);
            this.Head.NextNode = newNode;
        }

        /// <summary>
        ///     Add Node to end of LinkedList
        /// </summary>
        /// <param name="key"></param>
        /// <param name="item"></param>
        /// <history>
        ///     [Dylan]     4/22/2010   Fix issue#5974: AddLast(K key, T item) failed if LinkedList only has Head node
        ///                             This issue is found by unit test!
        ///                             Unit Test is Great, BUT, the more important thing is that make various test scenarioes.
        /// </history>
        public void AddLast(K key, T item)
        {
            Node<K, T> currentNode = this.Head;

            if (currentNode.NextNode == null)
            {
                // if LinkedList only has Head node, we should use "AddHead"
                AddHead(key, item);
            }
            else
            {
                while ((currentNode = currentNode.NextNode) != null)
                {
                    if (currentNode.NextNode == null)
                    {
                        Node<K, T> newNode = new Node<K, T>(key, item, null);
                        currentNode.NextNode = newNode;
                        break;
                    }
                }
            }
        }
         
        /// <summary>         
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public T Find(K key)
        {
            Node<K,T> current = Head;
            while (current.NextNode != null)
            {
                #region Code Understanding
                /// 1. we do:
                /// if(current.m_Key == key)
                /// Will not compile, get error:	Operator '==' cannot be applied to operands of type 'K' and 'K'
                /// compiler does not know whether K (or the actual type supplied by the client) supports the == operator. For example, structs by default do not provide such an implementation. 

                /// To advoid 1, 
                /// 2. we do:
                /// if (((IComparable)current.m_Key).CompareTo(key) == 0)  
                /// try to overcome the == operator limitation by using the IComparable interface.
                /// But, if m_Key type does not derive from System.Icomparable, when running, get exception:
                /// Unable to cast object of type '***(m_Key type)' to type 'System.IComparable'.

                /// To advoid 2,
                /// 3. we do: "Derivation Constraint"
                /// public class LinkedList<K,T> where K: IComparable               
                /// {...}
                /// which indicate to the compiler that the generic type parameter 'K' implements a particular interface IComparable. 

                /// then if class XXX does not implement the interface IComparable
                /// LinkedList<XXX, string> s = new LinkedList<XXX, string>();
                /// Compiler will defuse to build the code, get Error: 
                ///      The type 'XXX' cannot be used as type parameter 'K' in the generic type or method 'LinkedList<K,T>'. 
                ///      There is no implicit reference conversion from 'XXX' to 'System.IComparable'.	

                /// After 3, it does not eliminate the boxing penalty when the key used is a value type, such as an integer. 
                /// To overcome this, the System.Collections.Generic namespace defines the generic interface IComparable<T>:
                /// public interface IComparable<T> 
                /// {
                ///   int CompareTo(T other);
                ///   bool Equals(T other);
                /// }
                /// 4. we do 
                /// public class LinkedList<K,T> where K : IComparable<K>
                /// {...}
                /// by doing so you gain not only type safety but also eliminate the boxing of value types when used as keys:                    
                #endregion 
                if (current.m_Key.CompareTo(key) == 0)
                    return current.m_Item; 
                else
                    current = current.NextNode;
            }
            return default(T);            
        }

        public T this[K key]
        {
            get
            {
                return Find(key);
            }
        }

        /// <summary>
        ///  overload operators '+' for generic class "LinkedList<K, T>"
        /// </summary>
        /// <param name="lhs"></param>
        /// <param name="rhs"></param>
        /// <returns></returns>
        public static LinkedList<K,T> operator+(LinkedList<K,T> lhs,  LinkedList<K,T> rhs)
        {
            return concatenate(lhs,rhs);
        }

        /// <summary>
        /// concatenate 2 LinkedList
        /// </summary>
        /// <param name="list1">the first Linked List</param>
        /// <param name="list2">the second Linked List</param>
        /// <returns>the concatenated new LinkedList</returns>
        static LinkedList<K, T> concatenate(LinkedList<K, T> list1, LinkedList<K, T> list2)
        {
            LinkedList<K, T> newList = new LinkedList<K, T>();
            Node<K, T> current = list1.m_Head.NextNode;

            newList.AddHead(current.m_Key, current.m_Item);
            while ((current = current.NextNode) != null)
            {
                newList.AddLast(current.m_Key, current.m_Item);
            }

            current = list2.m_Head;
            while ((current = current.NextNode) != null)
            {
                newList.AddLast(current.m_Key, current.m_Item);
            }
            return newList;            
        }

        /// <summary>
        /// override Equals, 
        /// compare 2 LinkedList based on there Items' Key value
        /// </summary>
        /// <param name="obj"></param>
        /// <returns>true if equal</returns>
        public override bool Equals(object obj)
        {  
            if ((obj == null) || (!obj.GetType().Equals(this.GetType())))
            {
                return false;
            }

            LinkedList<K, T> tempObj = (LinkedList<K, T>)obj;

            Node<K, T> currentRight = tempObj.m_Head.NextNode;
            Node<K, T> currentLeft = this.m_Head.NextNode;

            bool isEqual = true;
            while ((currentRight = currentRight.NextNode) != null 
                && (currentLeft = currentLeft.NextNode) != null)
            {
                if (currentLeft.m_Key.CompareTo(currentRight.m_Key) != 0)
                {
                    isEqual = false;
                    break;
                }
            }

            return isEqual;
        }

        public override int GetHashCode()
        {
            int hash = this.m_Head.m_Key.GetHashCode();
            if (this.m_Head.NextNode != null)
            {
                hash ^= this.m_Head.m_Item.GetHashCode();
            }
            return hash;
        }
    }
}
